#include <bits/stdc++.h>
using namespace std;
// https://leetcode.cn/problems/longest-valid-parentheses/description/
// 栈可以用来解决括号匹配问题，左括号push，右括号pop
class Solution {
public:
    int longestValidParentheses(string s) {
        //将一个无法匹配的括号的位置全部置1
        stack<int> st;
        vector<int> mark(s.size(),0);
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')st.push(i);
            else
            {
                if(st.empty())mark[i]=1;
                else st.pop();
            }
        }
        //删除多余的左括号
        while(!st.empty())
        {
            mark[st.top()]=1;
            st.pop();
        }
        int maxlen=0,res=0;
        for(int i=0;i<mark.size();i++)
        {
            if(!mark[i])res++;
            else res=0;
            maxlen=max(maxlen,res);
        }
        return maxlen;
    }
};
